#include <iostream>
#include <vector>
#include <memory>
#include <type_traits>
#include <algorithm>

template <typename Key, typename Value, int Order = 3>
class BPlusTree {
public:
	using key_type = std::decay_t<Key>;
	using value_type = std::decay_t<Value>;

	using non_ptr_key_type = std::remove_pointer_t<key_type>;
	using non_ptr_value_type = std::remove_pointer_t<value_type>;

private:
	struct Node {
		bool is_leaf;
		std::vector<non_ptr_key_type> keys;
		std::vector<std::unique_ptr<Node>> children;
		std::vector<non_ptr_value_type> values;

		Node(bool is_leaf) : is_leaf(is_leaf) {}

		bool is_full() const {
			return keys.size() == Order - 1;
		}
	};

	std::unique_ptr<Node> root;

public:
	BPlusTree() : root(std::make_unique<Node>(true)) {}

	void insert(const non_ptr_key_type& key, const non_ptr_value_type& value) {
		if (root->is_full()) {
			auto new_root = std::make_unique<Node>(false);
			new_root->children.push_back(std::move(root));
			split_child(new_root.get(), 0);
			root = std::move(new_root);
		}
		insert_non_full(root.get(), key, value);
	}

	void remove(const non_ptr_key_type& key) {
		remove(root.get(), key);
		if (root->keys.empty() && !root->is_leaf) {
			root = std::move(root->children[0]);
		}
	}

	const non_ptr_value_type* search(const non_ptr_key_type& key) const {
		return search(root.get(), key);
	}

private:
	void split_child(Node* parent, int index) {
		auto& node = parent->children[index];
		auto new_node = std::make_unique<Node>(node->is_leaf);

		for (int i = 0; i < Order / 2; ++i) {
			new_node->keys.push_back(std::move(node->keys[i + Order / 2]));
			if (!node->is_leaf) {
				new_node->children.push_back(std::move(node->children[i + Order / 2]));
			} else {
				new_node->values.push_back(std::move(node->values[i + Order / 2]));
			}
		}

		if (!node->is_leaf) {
			new_node->children.push_back(std::move(node->children[Order - 1]));
		} else {
			new_node->values.push_back(std::move(node->values[Order / 2]));
		}

		node->keys.resize(Order / 2);
		if (node->is_leaf) {
			node->values.resize(Order / 2);
		} else {
			node->children.resize(Order / 2 + 1);
		}

		parent->keys.insert(parent->keys.begin() + index, new_node->keys[0]);
		parent->children.insert(parent->children.begin() + index + 1, std::move(new_node));
	}

	void insert_non_full(Node* node, const non_ptr_key_type& key, const non_ptr_value_type& value) {
		if (node->is_leaf) {
			auto pos = std::lower_bound(node->keys.begin(), node->keys.end(), key);
			int index = pos - node->keys.begin();
			node->keys.insert(pos, key);
			node->values.insert(node->values.begin() + index, value);
		} else {
			auto pos = std::upper_bound(node->keys.begin(), node->keys.end(), key);
			int index = pos - node->keys.begin();
			if (node->children[index]->is_full()) {
				split_child(node, index);
				if (key > node->keys[index]) {
					++index;
				}
			}
			insert_non_full(node->children[index].get(), key, value);
		}
	}

	void remove(Node* node, const non_ptr_key_type& key) {
		if (node->is_leaf) {
			auto pos = std::lower_bound(node->keys.begin(), node->keys.end(), key);
			if (pos != node->keys.end() && *pos == key) {
				node->keys.erase(pos);
				node->values.erase(node->values.begin() + (pos - node->keys.begin()));
			}
		} else {
			auto pos = std::upper_bound(node->keys.begin(), node->keys.end(), key);
			int index = pos - node->keys.begin();
			if (pos != node->keys.begin() && *(pos - 1) == key) {
				// Key is present in the internal node, replace it with its predecessor
				node->keys[index - 1] = get_max_key(node->children[index - 1].get());
				remove(node->children[index - 1].get(), node->keys[index - 1]);
			} else {
				remove(node->children[index].get(), key);
			}
		}
	}

	non_ptr_key_type get_max_key(Node* node) const {
		while (!node->is_leaf) {
			node = node->children.back().get();
		}
		return node->keys.back();
	}

	const non_ptr_value_type* search(Node* node, const non_ptr_key_type& key) const {
		auto pos = std::lower_bound(node->keys.begin(), node->keys.end(), key);
		if (pos != node->keys.end() && *pos == key) {
			if (node->is_leaf) {
				return &node->values[pos - node->keys.begin()];
			} else {
				return search(node->children[pos - node->keys.begin() + 1].get(), key);
			}
		} else {
			if (node->is_leaf) {
				return nullptr;
			} else {
				return search(node->children[pos - node->keys.begin()].get(), key);
			}
		}
	}
};

int main() {
	BPlusTree<int, std::string> tree;
	tree.insert(1, "one");
	tree.insert(2, "two");
	tree.insert(3, "three");
	tree.insert(4, "four");
	tree.insert(5, "five");

	const auto* value = tree.search(3);
	if (value) {
		std::cout << *value << std::endl; // Output: three
	}

	tree.remove(3);

	value = tree.search(3);
	if (!value) {
		std::cout << "Value not found" << std::endl; // Output: Value not found
	}

	return 0;
}
